package com.zlk.algorithm.algorithm.dynamicPlan;

import java.util.Arrays;

// 解码方法
// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
// 例如，"11106" 可以映射为："AAJF"、"KJF"
// 注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F"
// 这是由于 "6" 和 "06" 在映射中并不等价
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
// 题目数据保证答案肯定是一个 32位 的整数
// 测试链接 : https://leetcode.cn/problems/decode-ways/
public class Code03_DecodeWays {

    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
//        return f1(0,chars);
        int[] dp = new int[s.length()+1];
        Arrays.fill(dp,-1);
       // return f2(0,chars,dp);
        return f3(s.toCharArray());
    }


    /**
     * 情况
     * 1、当前字符不为0
     *    自己字符映射， 当前字符和下一个字符一起映射（可能会超长）
     *
     * 2、当前字符为0
     *    返回1  直接找下一伟
     *
     * @return
     */
    public int f1(int i,char[] chars){
        if(i>=chars.length){
            //为啥这个地方只需要判断是否越界就为1，因为，前面肯定是合法的不合法早就return 了,
            // 所以此处能走到肯定是满足一个场景的
            return 1;
        }
        //应为 0开头无法解码
        if(chars[i]=='0'){//
            return 0;
        }else{
            int a = f1(i + 1, chars);
            if (i + 1 < chars.length && ((chars[i] - '0') * 10 + chars[i + 1] - '0') <= 26) {
                a+=f1(i+2,chars);
            }
            return a;
        }
    }

    //记忆化搜索
    public int f2(int i,char[] chars,int[] dp){
        if(i==chars.length){
            dp[i] = 1;
            return 1;
        }
        if(dp[i]!=-1){
            return dp[i];
        }
        //应为 0开头无法解码
        if(chars[i]=='0'){//
            dp[i] = 0;
            return 0;
        }else{
            int a = f2(i + 1, chars,dp);
            if (i + 1 < chars.length && ((chars[i] - '0') * 10 + chars[i + 1] - '0') <= 26) {
                a+=f2(i+2,chars,dp);
            }
            dp[i] = a;
            return a;
        }
    }


    /**
     * 从低到顶的动态规划
     * @param
     * @param chars
     */
    public int f3(char[] chars){
        int[] dp =new int[chars.length+1];
        Arrays.fill(dp,-1);
        dp[chars.length] = 1;
        for (int i = chars.length-1; i>=0; i--) {
            if(chars[i]=='0'){//
                dp[i] = 0;
            }else{
                int a = dp[i+1];
                if (i + 1 < chars.length && ((chars[i] - '0') * 10 + chars[i + 1] - '0') <= 26) {
                    a+=dp[i+2];
                }
                dp[i] = a;
            }
        }
        return dp[0];
    }



    //思考：
    //1、从顶到底  字符拆分成char数组  每次遍历从左到右找 ，前面的位置每次固定+后面的可能出现的总数

    //位置的情况，
    // 1、当前位置为0 那就直接返回空，应为后续无法走  ，当前位置+后续位置 超过26 返回0 ，不超过走3
    // 2、当前位置直接转义
    // 3、当前位置+下一个位置转义

    /**
     * 从低到顶的动态规划
     * @param
     * @param chars
     */
    public int f4(char[] chars){
        int next = 1;
        int nnext = 0;
        for (int i = chars.length-1; i>=0; i--) {
            if(chars[i]=='0'){//
                nnext = next;
                next = 0;
            }else{
                int a = next;
                if (i + 1 < chars.length && ((chars[i] - '0') * 10 + chars[i + 1] - '0') <= 26) {
                    a+=nnext;
                }
                nnext = next;
                next = a;
            }
        }
        return next;
    }
}
